package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import LeetCode.interview._104_Maximum_Depth_of_Binary_Tree.TreeNode;
import sun.tools.jar.resources.jar;
import util.LogUtils;
import util.datastructure.RandomListNode;

/*
 * 
原题　
		 A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
	
	Return a deep copy of the list. 
题目大意

解题思路
	如果要copy一个带有random pointer的list，主要的问题就是有可能这个random指向的位置还没有被copy到，所以解决方法都是多次扫描list。
	
	第一种方法，就是使用HashMap来坐，HashMap的key存原始pointer，value存新的pointer。
	
		第一遍，先不copy random的值，只copy数值建立好新的链表。并把新旧pointer存在HashMap中。
		
		第二遍，遍历旧表，复制random的值，因为第一遍已经把链表复制好了并且也存在HashMap里了，所以只需从HashMap中，把当前旧的node.random作为key值，得到新的value的值，并把其赋给新node.random就好。
 	eg：
 		                  map:   [A, D]
 								 [B, E]
 								 [C, F]
 						//即：A节点(新链表中对应为D)的随机点为B, map.get(B)
 						  	得到 新链表中D对应的随机点为E
 			old链表[label,random]：A[1-2]->B[2-4]->C[3-1]->NULL;		
 			new链表[label,random]：D[1-2]->E[2-4]->F[3-1]->NULL;		
 * @Date 2017-10-05 23：31
 */
public class _138_Copy_List_with_Random_Pointer {
	
	/**
	 * 法一：使用HashMap
	 * @param head
	 * @return
	 */
    public RandomListNode copyRandomList(RandomListNode head) {
    	if (head == null)	return null;
    	//K..OldNode, V..NewNode
    	HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
    	RandomListNode pOldList = head, pNewHead = new RandomListNode(-1);	//临时头结点
    	RandomListNode pNewList = pNewHead;
    	//遍历链表 复制出新链表
    	while (pOldList != null) {
    		RandomListNode newNode = new RandomListNode(pOldList.label);
    		map.put(pOldList, newNode);
    		pNewList.next = newNode;			//复制出新链表 
    		pNewList = pNewList.next;
    		pOldList = pOldList.next;
    	}
    	pNewHead = pNewHead.next;				//去除临时头结点
    	
    	//加上random
    	pOldList = head;						//回到初始链表头、准备遍历
    	pNewList = pNewHead;
    	while (pOldList != null) {
    		pNewList.random = map.get(pOldList.random);
    		pOldList = pOldList.next;
    		pNewList = pNewList.next;
    	}
		return pNewHead;
    }
	public static void main(String[] args) {
		_138_Copy_List_with_Random_Pointer obj = new _138_Copy_List_with_Random_Pointer();

		obj.copyRandomList(null);
	}

}
